#include <iostream>
using namespace std;

struct node
{ int info;
  node *left;
  node *right;
};

node* maketree(int x, node* p, node *q)
{ node * r = new node;
  r->info = x;
  r->left = p;
  r->right = q;
  return r;
}

void preOrder(node * p)
{ if(p!=NULL)
  { cout << p->info << " ";
    preOrder(p->left);
    preOrder(p->right); 
  }
}

void inOrder(node * p)
{ if(p!=NULL)
  { inOrder(p->left);
    cout << p->info << " ";
    inOrder(p->right); 
  }
}

void postOrder(node * p)
{ if(p!=NULL)
  { postOrder(p->left);
    postOrder(p->right); 
    cout << p->info << " ";
  }
}

bool find(node *p, int x)
{ if(p==NULL) return false;
  if(x == p->info) return true;
  if(x < p->info) return find(p->left,x);
  return find(p->right,x);
}

int main()
{ node *p, *q, *r; 

  p = maketree(30,NULL,NULL);
  p = maketree(40,p,NULL);
  q = maketree(52,NULL,NULL);
  q = maketree(55,q,NULL);
  p = maketree(50,p,q);
  
  q = maketree(77,NULL,NULL);
  q = maketree(70,NULL,q);
  r = maketree(83,NULL,NULL);
  r = maketree(90,r,NULL);
  q = maketree(80,q,r);
  
  node * root = maketree(60,p,q);
         
//  preOrder(root); cout << " K-L-D" << endl;
  inOrder(root);  cout << " L-K-D" << endl;   
//  postOrder(root);  cout << " L-D-K" << endl;   
   
//  cout << "Nodes: " << nodeCnt(root) << endl; 
//  cout << "Heigth: " << heigth(root) << endl; 
  
  int x;
  do
  { cout << "x = ";
    cin >> x;
    if(find(root,x)) cout << "Found" << endl;
    else cout << "Not found" << endl;
  } while(x>0);
  

  return 0;
}
